This invention is related to the increasing of discrete information storage capacity in memory devices. Memory devices typically store discrete information in cells, whereby information is encoded by means of setting, or writing, the value of certain physical variables of said cells, characteristic of the memory device technology. Said cells may consist of some kind of transistor in a semiconductor memory (such as the so called flash memory), or a small allocated area of some optical media (such as the so called CD or DVD) or magnetic media (such as the so called HD).
Said physical variables would be, for example, some optical property in optical memory devices, some magnetic property in magnetic memory devices, some electrical property such as electrons charge or voltage in semiconductor memory, etc. Physical constraints would typically limit the smallest allowable physical variable value to some value, say b, the largest physical variable value to some other value a>b, so that the resulting allowable said physical variable value range is (a−b).
Encoding information, in regards to this proposed invention, is discrete in nature, that is both information and the corresponding physical variables are assumed to take values out of two corresponding predefined finite sets of values. The storing of information incurs then the mapping of a (say integer, or equivalently binary) piece of information into the value (or values) of said physical variable, and then the setting of a cell (or a group of cells) to that said value (or values), said setting usually called memory writing or programming. It is possible to measure the storage capacity of a memory by the largest integer that may possibly be written into it, or equivalently, by the number of binary units (bits) required to represent said largest integer.
Recovery of stored information involves the sensing or read-back of the value (or values) of said programmed physical variable of said cell (or group of cells); due to physical phenomena both said memory programming and this said read-back are generally noisy in nature and the value of the read back physical variable (which belongs to the continuum rather than to the discrete domain) differs from the originally (discrete) mapped value(s). Said information recovery then incurs two actions: first, the association of the (continuous) read back value(s) to the closest discrete permissible value(s) of said physical variable, usually called detection; and second, the decoding of said selected detected permissible value(s) back into the said piece of information (say integer, or equivalently binary) value.
There exist at least three ways to increase said storage capacity, namely:                a. increasing the number of memory cells in a device; this in general directly affects the cost of said device;        b. increasing the storage capacity of individual memory cells, by letting each cell store more than one bit; this can be achieved by setting the allowable number of discrete values of said physical variable to more than two; for example, in current art non-volatile, so called flash, semiconductor memory, c (=2 or more) bits-per-cell (bpc) are sometimes stored by letting the number of permissible discrete values be 2c (=4 or more); since as noted above the range of permissible discrete values is limited to (a−b), the exponential increase of required number of discrete values with the increase in number of bits-per-cell rapidly decreases the minimal distance, denoted 2r, between permissible values affecting the reliability of the read back i.e. increasing the probability of a bit error event;        c. enhancing the information encoding efficiency; as will be readily shown this can be achieved by considering information encoding as a so called sphere packing problem, by collectively encoding a block or piece of information (rather than a single bit or small group of bits) into a set of cells (rather than into a single cell).        
This proposed invention, while fully compatible with the fore-mentioned first two ways of memory storage capacity increase, deals specifically with said third way of storage capacity increase.
The sphere packing problem in a multi-dimensional space Rn has been extensively studied (e.g. [1], [2], [3]). Loosely stated it consists of finding ways to place as many as possible ‘solid’ hyper-spheres of radius r in a specified region of Rn; by ‘solid’ we mean that hyper-spheres are allowed to touch each other, but not to overlap.
The application of sphere packing concepts to memory storage and communication systems capacity increase has been proposed in [3] as early as 1999 (and possibly earlier) where, quoted, “ . . . We begin by describing the second main application of sphere packings, the design of signals for data transmission or storage systems”, and also “ . . . From now on we shall just describe the data transmission problem always keeping in mind that there are identical results for data storage systems”. However: no solution is provided in [3] to the information encoding/decoding associated essential problem, whereby a one-to-one mapping is required between a bounded integers set and lattice points confined to a hyper-cube (or to some other closed region) of lattice space.
The application of sphere packing concepts to memory storage has been also proposed in [4]. However, strict constraints were imposed in [4] on r and on (a−b), the respectively fore-mentioned hyper-spheres radius and physical variable permissible range and a specialized encoding/decoding method which fits very specific sphere packings was devised. As result of these strict constraints and specialized encoding method of [4] only relatively very modest memory storage capacity gains were achieved. For example, for a memory sphere packing structure in Rn, n=16 and supporting a nominal density c=1 bpc it is quoted ([4]) that “The method detailed above . . . which has been demonstrated on codes for 16 cells, with an information gain of 25%, is directly applicable to higher orders for 32, 64, 128 etc. cells” and also “A gain of 50% is attainable for n≧128”. By ‘nominal density’ we mean in the sequel the bit density achieved by spheres of given radius, confined to a cube of given size, and packed by means of the simplest integer (or cubic) lattice Zn as further detailed below.
It should also be noted that increasing the dimension of our space Rn has direct impact on the memory latency (i.e. the time period required to program and/or to read back memory information) and/or on cost of the memory cell sensing resources (such as so called analog-to-digital converters), the memory cell programming resources (including so called digital-to-analog converters) and the required computational power to encode, to detect, and to decode memory information. Hence it would be beneficial to achieve as much storage capacity gain as possible at the lowest possible space dimension n.
It is then the goal of this proposed invention to significantly improve the achievable memory storage capacity gain; for example, it will be demonstrated in the sequel that for a memory structure with nominal c=1 bpc (as in [4]) a memory storage capacity potential gain of 50% is possible with n=8 (compared with n≧128 in [4]), a potential gain of 75% is possible with n=16 (compared with 25% in [4]), a potential gain of 100% is possible with n=24, and even higher gains are possible for even larger space dimensions n.
Said possible memory storage capacity gains of our proposed invention are made possible, by a. the exploitation of ‘dense’ lattices for a most efficient solution of the sphere packing problem; b. the introduction of a novel and computationally simple encoding and decoding method; and c. (weak) relaxation of the hyper-sphere radius r constraint and/or of the physical variables (a−b) permissible range.